﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Sol169
{


    public int MajorityElement2(int[] nums)//先来一个暴力解法

    {
        Dictionary<int, int> map = new Dictionary<int, int>();
        int len = nums.Length;
        for (int i = 0; i < len; i++)
        {

            if (map.TryGetValue(nums[i], out int times))
            {
                map[nums[i]]++;
                //times++;
            }
            else
            {
                map[nums[i]] = 1;
            }

            //map[nums[i]]++;
        }

        int maxKey = -1;
        int maxValue = -1;
        //可以优化一下，边遍历边记录最大值
        foreach (var pair in map)
        {
            Console.WriteLine("key:" + pair.Key + "   val:" + pair.Value);

            if (pair.Value > maxValue)
            {
                maxValue = pair.Value;
                maxKey = pair.Key;
            }
            Console.WriteLine("maxKey:" + maxKey + "   maxValue:" + maxValue);
        }
        return maxKey;

    }
    public int MajorityElement3(int[] nums)//排序之后取中间的数

    {
        Array.Sort(nums);
        return nums[nums.Length / 2];



    }
    public int MajorityElement4(int[] nums)//投票法，时间O(n),空间O(n)数组

    {

        int len = nums.Length;

        int[] winner=new int[len];//这个数组不需要也可以，只需要记录当前数组（一样的）里面的元素和数量就可以了
        int winnerIndex = 0;
        
        
        for (int i = 0; i < len; i++)
        {
            if (winnerIndex ==0|| nums[i] == winner[winnerIndex-1])//遇到相同的进队，或者空的时候也入队
            {
                winner[winnerIndex++] = nums[i];
             
            }
            else
            {//winner里面的数组出来同归于尽一个

                winnerIndex--;
            } 


        }
        return winner[0];


    }public int MajorityElement(int[] nums)//投票法，时间O(n),空间O(1)

    {

        int len = nums.Length;

        //int[] winner=new int[len];//这个数组不需要也可以，只需要记录当前数组（一样的）里面的元素和数量就可以了
        int winnerIndex = 0;//当前胜者投票数
        int winer = 0;//当前胜者


        for (int i = 0; i < len; i++)
        {
            if (winnerIndex ==0|| nums[i] == winer)//遇到相同的进队，或者空的时候也入队
            {
                winer = nums[i];
                winnerIndex++;
            }
            else
            {//winner里面的数组出来同归于尽一个

                winnerIndex--;
            } 


        }
        return winer;


    }


}

class Program
{
    static void Main169(string[] args)
    {

        //int[] nums = { 3, 2, 3 };
        //int[] nums = { 2, 2, 1, 1, 1, 2, 2 };
        int[] nums = { 4, 3, 2, 1, 2, 2, 2 };
        //int[] nums = { 1, 1, 1, 1, 1, 1, 8 };

        Sol169 sol
            = new Sol169();
        int res = sol.MajorityElement(nums);
        Console.WriteLine(res);



    }
}
